package 蓝桥杯十二;
import java.util.List;
import java.util.ArrayList;
public class D {
	/**
	 * 再来 补充一个 递归 回溯的 版本
	 * 先对 数组 排序 然后 可以 进行剪枝 的操作 不排序 也是 可以的
	 * 非常标准的 递归 回溯 代码
	 * 而且 下面 这个 代码 还是 改成动态规划的 
	 * 而且 还是 很好 改 的
	 * 还是问题原型是什么 
	 */
	public static int backTracing(int []arr,int mulpity,int index,int aim) {
		if(mulpity  == aim) {
			return 1;
		}
		if(index ==  arr.length) {
			return 0;
		}
		/**
		 * 这种 就是 不排序  不剪枝的 代码 
		 * int ans = 0;
		 * for(int i - index ;i < arr.length; i++){
		 * 		if(arr[i] * mulpity <= aim){
		 * 			ans += backTracing(arr,mulpity,i+1, aim);
		 * }
		 * return ans;
		 */
		int ans  = 0;
		for(int i = index ;i < arr.length && arr[i] * mulpity <= aim;i++) {
			ans += backTracing(arr,mulpity * arr[i], i + 1,aim);
		}
		return ans;
	}
	public static void main(String []args) {
		prime(120);
//		cal(60);
//		cal(2021041820210418l);
//		prime(2021041820210418l);
	}
	
	
	/**基本 算术定理  或者 (质数 因子 定理)
	 * 
	 * 直接  枚举 所有的 因数 
	 * 这个 题 可以这样 思考一下 ：
	 * 假设 ： a * b * c = n
	 *   令   x = a * b； ---> x * c = n 这不是 相当于 n 的 两个因子 嘛   
	 * 所以 为啥 可以 枚举 所有的 因子 之和  来计算 
	 * @param n
	 */
	public static void cal(long n) {
		List<Long> list = new  ArrayList<>();
		for(long i = 1;i <= n/i;i++) {
			if(n % i == 0) {
				list.add(i);
				if( n/i != i) {
					list.add(n/i);
				}
			}
		}
		int ans = 0;
/**
 * 这里 怎么 说  是不是 可以 来个 
 * 两 数  之和 的  三数 之和   四数之和 的 拓展
 *两数 之积 ，三数 之积 ，四数 之 积的  发展 
 *等到 比赛 后 再去 好好的思考 一下 这个 问题
 */
//		System.out.println(list);
		for(Long i : list) {
			for(long j :list) {
				/**
				 * 想一想 怎样 才能 直接 不用 枚举 k 
				 * 直接 把 第三层 for 循环 给省掉 ？
				 */
				for(long k : list) {
					if(i * j * k == n)ans++;
				}
				
				
			}
		}
		System.out.println(ans);
	}
	
	
	
	
	
	public static long prime(long n,long x) {
		for(int i = 2;i <= n/i; i++) {
			long a = 0;
			long b = 0;
			/**
			 * a 是  n 的 一个 质因子
			 * b  是 a 的 指数 
			 * 因为 一个 数一定可以  拆为 质因子 指数和 的形式
			 * 
			 */
			while(n % i == 0) {
				a = i;
				b++;
				n /= i;
			}
		}
		return 1L;
	}
	/**
	 * 
	 * 下的 代码 是 计算 质因数 
	 * 博客地址：
	 * https://blog.csdn.net/GD_ONE/article/details/104579936
	 * @param n
	 */
	public static void prime(long n){
	    for(long i = 2; i <= n / i; i++){
	        long a = 0, b = 0;
	        while(n % i == 0){
	            a = i;
	            n /= i;
	            b++;
	        }
	        if(b > 0)
	            System.out.println(a + " " + b);
	    }
	    if(n > 1) System.out.println(n + " " + 1);
	}
	

}
